package  main.java.leetcode.editor.cn;
//2022-04-05 16:20:08
//给定两个整数 a 和 b ，求它们的除法的商 a/b ，要求不得使用乘号 '*'、除号 '/' 以及求余符号 '%' 。 
//
// 
//
// 注意： 
//
// 
// 整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2 
// 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231, 231−1]。本题中，如果除法结果溢出，则返回 231 − 1 
// 
//
// 
//
// 示例 1： 
//
// 
//输入：a = 15, b = 2
//输出：7
//解释：15/2 = truncate(7.5) = 7
// 
//
// 示例 2： 
//
// 
//输入：a = 7, b = -3
//输出：-2
//解释：7/-3 = truncate(-2.33333..) = -2 
//
// 示例 3： 
//
// 
//输入：a = 0, b = 1
//输出：0 
//
// 示例 4： 
//
// 
//输入：a = 1, b = 1
//输出：1 
//
// 
//
// 提示: 
//
// 
// -231 <= a, b <= 231 - 1 
// b != 0 
// 
//
// 
//
// 注意：本题与主站 29 题相同：https://leetcode-cn.com/problems/divide-two-integers/ 
//
// 
// Related Topics 位运算 数学 
// 👍 122 👎 0

class Xoh6Oh {
    public static void main(String[] args) {
        //创建该题目的对象方便调用
        Solution solution = new Xoh6Oh().new Solution();
        int a = -2147483648;
        int b = 1;
        System.out.println(solution.divide(a, b));
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int divide(int a, int b) {
            //特殊情况1, b=1
            if (b == 1){
                return a;
            }
            //特殊情况2, b=-1
            if (b == -1){
                return a == Integer.MIN_VALUE ? Integer.MAX_VALUE : -a;
            }
            //特殊情况3, a=0
            if (a == 0){
                return 0;
            }
            //确定符号
            boolean positive = (a ^ b) >= 0;
            //为避免溢出, 转换为负数进行计算
            a = a < 0 ? a : -a;
            b = b < 0 ? b : -b;
            //快速相减
            int quotient = 0;
            while (a <= b){
                int base = 1;
                int divisor = b;
                //使用减法, 避免溢出
                while (a - divisor <= divisor){
                    divisor <<= 1;
                    base <<= 1;
                }
                quotient += base;
                a -= divisor;
            }
            return positive ? quotient : -quotient;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
